package com.JingYan.HuaWei;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: JingYan
 * @ClassName: JKC001.java
 * @author: DongJiaQi
 * @version: 1.0.0
 * @Description: 华为机考C卷 亲子游戏
 * @createTime 2024年04月11日 17:06:00
 */
public class JKC001 {
    /**
     * 宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
     *
     * 游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
     *
     * 请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
     */

    public static class call {
        //坐标,步数,糖果数
        int x,y,bs,tgs;
        public call(int x, int y, int bs, int tgs) {
            this.x = x;
            this.y = y;
            this.bs = bs;
            this.tgs = tgs;
        }
    }
    public static int collectCandies(int[][] grid, int[] momPos, int[] babyPos) {
        // 格子
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Queue<call> queue = new LinkedList<>();

        queue.add(new call(momPos[0],momPos[1],0,0));
        visited[momPos[0]][momPos[1]] = true;
        // 右、左、下、上
        int [][] fx = {{0,1},{0,-1},{1,0},{-1,0}};
        int maxTgs=-1;
        int minBs = Integer.MAX_VALUE;
        boolean nextFlag = false;
        while (!queue.isEmpty()) {
            call cur = queue.poll();
            if(cur.x==babyPos[0]&&cur.y==babyPos[1]){
                if(cur.bs<=minBs){
                    minBs =Math.max(maxTgs,cur.tgs);
                    minBs=cur.bs;
                }

                nextFlag =true;
                continue;
            }
            for (int[] ints : fx) {
                int nextXFx = ints[0];
                int nextYFx = ints[1];
                int nextX = nextXFx + cur.x;
                int nextY = nextYFx + cur.y;
                //判断是否超界
                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) {
                    continue;
                }
                //判断是否障碍
                if (grid[nextX][nextY] == -1) {
                    continue;
                }
                //判断是否是回头路
                if(visited[nextX][nextY]==true){
                    continue;
                }
                if (!nextFlag){
                    queue.add(new call(nextX,nextY,cur.bs+1,cur.tgs+grid[nextX][nextY]));
                    visited[nextX][nextY] = true;
                }

            }

        };
       return maxTgs;

    }

    public static void main(String[] args) {
        int[][] grid = {
                {0, 1, -1, 0, 1},
                {0, -1, 1, 0, -1},
                {1, 0, -1, 1, 0},
                {-1, 0, 1, 0, 1},
                {1, 1, 0, 1, 0}
        };
        int[] momPos = {0, 0};
        int[] babyPos = {4, 4};

        System.out.println("Maximum candies collected: " + collectCandies(grid, momPos, babyPos));
    }
}
